// https://leetcode.cn/problems/maximum-length-of-pair-chain/

// 题干：给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。
//      现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。
//      找出并返回能够形成的 最长数对链的长度 。
//      你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

// 示例：输入：pairs = [[1,2], [2,3], [3,4]]
//      输出：2

// 碎语：因为可以任意选，所以先排序一下进行预处理，其余跟最长递增子序列相同

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    static bool cmp(const vector<int>& pair1, const vector<int>& pair2)
    {
        return pair1[0] < pair2[0];
    }
    int findLongestChain(vector<vector<int>>& pairs)
    {
        int n = pairs.size(), ret = 1;
        if (n == 1) return 1;

        // 先对矩阵排个序
        sort(pairs.begin(), pairs.end(), cmp);

        // dp方程构建
        vector<int> dp(n ,1);
        for (int i = 1 ; i < n ; i++){
            for (int j = 0 ; j < i ; j++){
                if (pairs[i][0] > pairs[j][1]) dp[i] = max(dp[i], dp[j] + 1);
            }
            ret = max(ret, dp[i]);
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<vector<int>> pairs = {{1, 2}, {2, 3}, {3, 4}};

    cout << sol.findLongestChain(pairs) << endl;

    return 0;
}












